
/////////////////////////////////////////////////////////////////////////////////
//
//  线性表 ： https://www.cnblogs.com/choon/p/3876606.html
//
/////////////////////////////////////////////////////////////////////////////////

#include<iostream>

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef int ElemType;

typedef struct{
    ElemType *elem;
    int length;
    int size;
} SqList;

int List_Init(SqList &L)
{
    //开辟一个存储空间，并把这块存储空间的基地址赋值给elem
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L.elem)
    {
        return -1;              //空间分配失败
    }

    L.length = 0;               //当前长度
    L.size = LIST_INIT_SIZE;    //当前分配量
    return 0;
}

int List_Find(SqList &L, ElemType target)
{
    int pos = -1;
    for (int i = 0; i < L.length;i++)
    {
        if(L.elem[i] == target)
        {
            pos = i;
            break;
        }
    }
    return pos ;
}

int List_Insert(SqList &L, int i, ElemType target)
{
    // 判断插入位置， 在 0 到 length 之间 ,从 第一元素 到 最后一个元素的后一个位置 之间。
    if(i<0 || i> L.length )
    {
        return -1;
    }

    // 是否需要扩展空间
    if(L.length >= L.size)
    {
        // TODO , 扩展空间
        ElemType *newSpace = (ElemType *)realloc(L.elem, (L.size + LISTINCREMENT)*sizeof(ElemType));
        if (!newSpace) return -1;   //存储空间分配失败
        L.elem = newSpace;          //新基址
        L.size += LISTINCREMENT;    //增加存储容量
    }

    // 插入元素
    ElemType *pos, *p ;
    pos = &(L.elem[i]);     // 用 pos 记录第i个元素的地址

    // 从尾部开始后移 。
    for (p = &(L.elem[L.length-1]); p >= pos;p--)
    {
        *(p + 1) = *p;
    }
    *pos = target;
    L.length++;

    return 0;
}

int List_Remove(SqList &L, int i, ElemType *target=nullptr)
{
    // 判断删除位置， 在 0 length-1 （当前元素个数）之间。
    if(i<0 || i> L.length-1 )
    {
        return -1;
    }

    if(target!=nullptr)
    {
        *target = L.elem[i];
    }

    for (; i < L.length;i++)
    {
        L.elem[i] = L.elem[i+1];
    }
    L.length-- ;
    return 0;
}


void showList(SqList &lst)
{
    for (int i = 0; i < lst.length; i++)
    {
        std::cout << lst.elem[i] << " ";
    }
    std::cout << std::endl;
}
int main()
{
    // 初始化
    SqList lst;
    List_Init(lst);

    // 插入10个数字给线性表list
    for (int i = 0; i < 10; i++)
    {
        List_Insert(lst, i, i);
    }
    showList(lst);

    int pos = List_Find(lst, 6);
    std::cout <<" 6 at " << pos <<std::endl;

    //删除位置 5 的元素 5
    ElemType e;
    List_Remove(lst, 5,&e);
    showList(lst);

    //在第2个位置插入一个元素-1
    List_Insert(lst, 2, -1);
    showList(lst);
    return EXIT_SUCCESS;
}

